package com.kehao.leetcode.hard.backtracking;

import org.junit.Test;

import java.util.*;

public class RemoveInvalidParenthesesSolution {
    private int maxDepth = Integer.MAX_VALUE;
    private Map<String,Boolean> vaildMap = new HashMap<>();
    private Set<String> visited = new HashSet<>();

    public List<String> removeInvalidParentheses(String s) {
        Set<String> result = new HashSet<>();
        getResult(s,1,result);
        return new ArrayList<>(result);
    }

    private void getResult(String s, int depth,Set<String> result) {
        if(visited.contains(s)) return;
        visited.add(s);
        if(depth>maxDepth) return;
        if(depth == maxDepth){
            if(isVaild(s)){
                result.add(s);
                return;
            }
        }
        if(isVaild(s)){
            maxDepth = depth;
            result.clear();
            result.add(s);
            return;
        }else {
            Set<String> set = new HashSet<>();
            for (int i = 0; i < s.length(); i++) {
                if(s.charAt(i)=='('||s.charAt(i)==')'){
                    set.add(s.substring(0,i)+s.substring(i+1));
                }
            }
            for (String str : set) {
                getResult(str,depth+1,result);
            }
        }
    }

    private boolean isVaild(String s){
        if(vaildMap.containsKey(s)) return vaildMap.get(s);
        int code = 0;
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)=='(') code++;
            else if(s.charAt(i)==')') code--;
            if(code<0){
                vaildMap.put(s,false);
                return false;
            }
        }
        if(code==0){
            vaildMap.put(s,true);
            return true;
        }else {
            vaildMap.put(s,false);
            return false;
        }
    }

    @Test
    public void test01(){
        String s = "()())()";
        System.out.println(removeInvalidParentheses(s));
    }

    @Test
    public void test02(){
        String s = "(a)())()";
        System.out.println(removeInvalidParentheses(s));
    }

    @Test
    public void test03(){
        String s = ")(";
        List<String> result = removeInvalidParentheses(s);
        System.out.println(result);
    }

    @Test
    public void test04(){
        String s = "((()";
        System.out.println(removeInvalidParentheses(s));
    }
    @Test
    public void test05(){
        String s = ")))(z)(x)((()()";
        System.out.println(removeInvalidParentheses(s));
    }
}
